import java.util.LinkedList;
import java.util.List;

/**
 * 784. 字母大小写全排列
 * https://leetcode.cn/problems/letter-case-permutation/description/
 */
class Solution3 {
    StringBuilder path;
    List<String> ret;
    public List<String> letterCasePermutation(String s) {
        path = new StringBuilder();
        ret = new LinkedList<>();
        dfs(s, 0);
        return ret;
    }
    public void dfs(String s, int pos) {
        if(pos == s.length()) {
            ret.add(new String(path));
            return;
        }
        //不改变
        char ch = s.charAt(pos);
        path.append(ch);
        dfs(s, pos + 1);
        path.deleteCharAt(path.length() - 1);
        //改变
        if(ch < '0' || ch > '9') {
            char tmp = change(ch);
            path.append(tmp);
            dfs(s, pos + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
    public char change(char ch) {
        if(ch >= 'a' && ch <= 'z') return ch -= 32;//小写转大写
        else return ch += 32;//大写转小写
    }
}